home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / flxlstc.exe / FLEXLIST.CKR < prev    next >
Text File  |  1990-12-05  |  24KB  |  1,124 lines
  1. /*
  2.  
  3.     flexlist.ckr
  4.     10-4-90
  5.     Homogeneous-heterogeneous 
  6.     hybrid stack-queue-list-array generic class.
  7.     K&R C
  8.  
  9.     Copyright 1990
  10.     John W. Small
  11.     All rights reserved
  12.  
  13.     PSW / Power SoftWare
  14.     P.O. Box 10072,
  15.     McLean, Virginia 22102 8072
  16.     (703) 759-3838
  17.  
  18. */
  19.  
  20.  
  21. #include <flexlist.hkr>    /*  size_t, void, const  */
  22.  
  23. #ifdef ANSI_C_STD_LIB
  24.  
  25. #include <stdlib.h>     /*  malloc(), free()  */
  26. #include <string.h>    /*  memcpy(), memset()  */
  27.  
  28. #else
  29.  
  30. extern void *malloc(/* size_t size */);
  31. extern free(/* void *block */);
  32.  
  33. void *memcpy(dest, src, n)
  34. void *dest;
  35. const void *src;
  36. size_t n;
  37. {
  38.     if (dest && src && n)
  39.         while (n--) 
  40.             dest[n] = src[n];
  41.     return dest;
  42. }
  43.  
  44. void *memset(s, c, n)
  45. void *s;
  46. int c;
  47. size_t n;
  48. {
  49.     if (s && n)
  50.         while (n--)
  51.             s[n] = c;
  52.     return s;
  53. }
  54.  
  55. #endif
  56.  
  57.  
  58. /*  String variant FlexNode virtual functions  */
  59.  
  60. /*
  61.     FNnew() is called by FlexList functions (primitives)
  62.     that need to allocate new variant length FlexNodes,
  63.     e.g. FLpushD(), FLinsQD(), FLinsD(), FLinsSortD().
  64.     A pointer to the data to be placed in the new node
  65.     is passed to FNnew().  Your FNnew() function must
  66.     decide how large that data is and allocate a new 
  67.     FlexNode big enough to hold that data, i.e.
  68.  
  69.     FlexN N = malloc(sizeof(FlexNode) + 
  70.         sizeofYourData - 1).
  71.  
  72.     Your FNnew() function must also copy that data to
  73.     the new node.  "D" is never NULL!
  74.  
  75.     Please note that FNnew() could call a known function
  76.     pointer (function) in the data to determine its size.
  77.     It could also call another function to copy/
  78.     initialize the FlexNode data area from the data.
  79.     Data that contains its own functions for interfacing 
  80.     with itself are called objects.  Thus FlexLists can 
  81.     be made to hold polymorphic objects via the 
  82.     virtual function table functionology.
  83.  
  84.     Study all four virtual functions FNnew(), FNwrite(),
  85.     FNread(), and FNdestruct() for strings and how they
  86.     are called by the various FlexList functions to get
  87.     a better understanding of variant FlexLists.
  88. */
  89.  
  90. static FlexN FNnewStr(D)
  91. const void *D;
  92. {
  93.     FlexN N;
  94.     size_t i;
  95.  
  96.     for (i = 0; D[i++]; /* no reinit */)
  97.         /* null statement */;
  98.     if ((N = (FlexN) malloc(sizeof(FlexNode)+i-1)) != FlexN0)
  99.         memcpy(N->data,D,i);
  100.     return N;
  101. }
  102.  
  103.  
  104. /*  FNwrite() is called by FLstoreD() to write variant data
  105.     to a variant FlexNode.  FNwrite() returns true if
  106.     the write is successful.  Make sure the new data doesn't
  107.     write pass the end of the old.  "ND" and "D" are never 
  108.     NULL! */
  109.  
  110. static int FNwriteStr(ND, D)
  111. void *ND;
  112. const void *D;
  113. {
  114.     while (*ND)
  115.         if ((*ND++ = *D++) == '\0')
  116.             break;
  117.     return 1;
  118. }
  119.  
  120. /*  FNread() is called by FLtopD(), FLnextD(), 
  121.     FLprevD(), and FLrecallD() to read variant data
  122.     from a variant FlexNode.  FNread() returns true if
  123.     the read is successful or if there is no place to
  124.     read the data to.  "ND" and "D" are never NULL!  */
  125.  
  126. static int FNreadStr(ND, D)
  127. const void *ND;
  128. void *D;
  129. {
  130.     while ((*D++ = *ND++) != '\0')
  131.         /* null statement */;
  132.     return 1;
  133. }
  134.  
  135. /*  FNdestruct() is called by FLclear(), FLdelete() via 
  136.     Flclear(), FLpopD(), and FLdelD() to destruct
  137.     variant data in a FlexNode.  Please note that
  138.     references to suballocated memory may be copied
  139.     to the outgoing data structure instead of being
  140.     cloned and then deallocated.  You must keep any
  141.     scheme straight though.  FLclear() always passes
  142.     NULL to the second parameter of FNdestruct() via
  143.     a call to FLpopD(L,0),    however, so any 
  144.     suballocated memory must be freed in that case!
  145.     "ND" is never NULL but "D" can be!  */
  146.  
  147. static int FNdestructStr(ND, D)
  148. void *ND;
  149. void *D;
  150. {
  151.     if (D) 
  152.         while ((*D++ = *ND++) != '\0')
  153.             /* null statement */;
  154.     return 1;
  155. }
  156.  
  157. /*  Any of the virtual functions can be absent.  The FlexList
  158.     functions that call them will simply return a failure
  159.     indication.  Use FNnew0, FNwrite0, FNread0, and/or
  160.     FNdestruct0 as zero initializers.  */
  161.  
  162. FlexNodeVFT FlexNodeStrVFT = { 
  163.     FNnewStr, FNwriteStr, FNreadStr, FNdestructStr };
  164.  
  165.  
  166. /*  FlexList constructors/destructor - static headers */
  167.  
  168. #define FLzero(L) memset((void *)(L),0,sizeof(FlexList)-1)
  169.  
  170. FlexL FLfixed(L, sizeofNodeData)
  171. FlexL L;
  172. size_t sizeofNodeData;
  173. {
  174.     if (!L)  
  175.         return L;
  176.     /* (void) */ FLzero(L);
  177.     if (!sizeofNodeData || sizeofNodeData 
  178.         > FLmaxSizeofNodeData)
  179.         return FlexL0;
  180.     L->maxNodes = FLmaxMaxNodes;
  181.     L->sizeofNodeData = sizeofNodeData;
  182.     L->sizeofNode = sizeof(FlexNode) 
  183.         + sizeofNodeData - 1;
  184.     L->sorted = 1;
  185.     return L;
  186. }
  187.  
  188. FlexL FLunpack(L, sizeofCell, cells, array)
  189. FlexL L;
  190. size_t sizeofCell;
  191. unsigned cells;
  192. const void *array;
  193. {
  194.     if (!L) 
  195.         return L;
  196.     /* (void) */ FLzero(L);
  197.     if ((sizeofCell > FLmaxSizeofNodeData) ||
  198.         !sizeofCell || !cells || !array)
  199.         return FlexL0;
  200.     L->maxNodes = FLmaxMaxNodes;
  201.     L->sizeofNodeData = sizeofCell;
  202.     L->sizeofNode = sizeof(FlexNode) 
  203.         + sizeofCell - 1;
  204.     for (;cells && FLinsQD(L,array); cells--)
  205.         array = (char *) array + sizeofCell;
  206.     return L;
  207. }
  208.  
  209. FlexL FLvariant(L, vft)
  210. FlexL L;
  211. FlexNVFT vft;
  212. {
  213.     if (!L)
  214.         return L;
  215.     /* (void) */ FLzero(L);
  216.     if (!vft)
  217.         return FlexL0;
  218.     L->maxNodes = FLmaxMaxNodes;
  219.     L->sorted = 1;
  220.     L->vft = vft;
  221.     return L;
  222. }
  223.  
  224. int   FLclear(L)
  225. FlexL L;
  226. {
  227.     while (FLpopD(L,(void *)0))
  228.         /* null statement */;
  229.     if (L) if (!L->nodes)
  230.         return (L->sorted = 1);
  231.     return 0;
  232. }
  233.  
  234. /*  FlexList constructors/destructor - dynamic headers  */
  235.  
  236. /*  FlexList headers are flagged as dynamic if and only if
  237.     FLDdestruct != NULL.  FLDmalloced() is the default
  238.     function pointer whenever one isn't specified.  */
  239. /* ARGSUSED */ 
  240. static int FLDmalloced(LD)
  241. void *LD;
  242. {    /*  LD is intentionally unused!  */
  243.     return 1;
  244. }
  245.  
  246. static FlexL FLnew(sizeofLocalData, FLDdestruct)
  247. size_t sizeofLocalData;
  248. int (*FLDdestruct)(/* void *LD */);
  249. {
  250.     FlexL L;
  251.  
  252.     if (sizeofLocalData > FLmaxSizeofLocalData) 
  253.         return FlexL0;
  254.     L = (FlexL) malloc(sizeof(FlexList) + 
  255.         sizeofLocalData - 1);
  256.     if (L)  {
  257.         /* (void) */ FLzero(L);
  258.         if (FLDdestruct)
  259.             L->FLDdestruct = FLDdestruct;
  260.         else
  261.             L->FLDdestruct = FLDmalloced;
  262.     }
  263.     return L;
  264. }
  265.  
  266. FlexL FLfixedNew(sizeofNodeData, sizeofLocalData, 
  267.     FLDdestruct)
  268. size_t sizeofNodeData;
  269. size_t sizeofLocalData;
  270. int (*FLDdestruct)(/* void *LD */);
  271. {
  272.     FlexL L;
  273.  
  274.     if (!sizeofNodeData || sizeofNodeData > 
  275.         FLmaxSizeofNodeData) 
  276.         return FlexL0;
  277.     if ((L = FLnew(sizeofLocalData,FLDdestruct)) 
  278.         != FlexL0)  {
  279.         L->maxNodes = FLmaxMaxNodes;
  280.         L->sizeofNodeData = sizeofNodeData;
  281.         L->sizeofNode = sizeof(FlexNode) 
  282.             + sizeofNodeData - 1;
  283.         L->sorted = 1;
  284.     }
  285.     return L;
  286. }
  287.  
  288. FlexL FLunpackNew(sizeofCell, cells, array,
  289.     sizeofLocalData, FLDdestruct)
  290. size_t sizeofCell;
  291. unsigned cells;
  292. const void *array;
  293. size_t sizeofLocalData;
  294. int (*FLDdestruct)(/* void *LD */);
  295. {
  296.     FlexL L;
  297.  
  298.     if ((sizeofCell > FLmaxSizeofNodeData) ||
  299.         !sizeofCell || !cells || !array)
  300.         return FlexL0;
  301.     if ((L = FLnew(sizeofLocalData,FLDdestruct)) 
  302.         != FlexL0)  {
  303.         L->maxNodes = FLmaxMaxNodes;
  304.         L->sizeofNodeData = sizeofCell;
  305.         L->sizeofNode = sizeof(FlexNode) 
  306.             + sizeofCell - 1;
  307.         for (;cells && FLinsQD(L,array); cells--)
  308.             array = (char *) array + sizeofCell;
  309.     }
  310.     return L;
  311. }
  312.  
  313. FlexL FLvariantNew(vft, sizeofLocalData, FLDdestruct)
  314. FlexNVFT vft;
  315. size_t sizeofLocalData;
  316. int (*FLDdestruct)(/* void *LD */);
  317. {
  318.     FlexL L;
  319.  
  320.     if (!vft) 
  321.         return FlexL0;
  322.     if ((L = FLnew(sizeofLocalData,FLDdestruct)) 
  323.         != FlexL0)  {
  324.         L->maxNodes = FLmaxMaxNodes;
  325.         L->sorted = 1;
  326.         L->vft = vft;
  327.     }
  328.     return L;
  329. }
  330.  
  331. int FLdelete(Lptr)
  332. FlexL *Lptr;
  333. {
  334.     if (!Lptr) 
  335.         return 0;
  336.     if (!(*Lptr)->FLDdestruct) 
  337.         return 0;
  338.     if (!(*((*Lptr)->FLDdestruct))((*Lptr)->data))
  339.         return 0;
  340.     if (!FLclear(*Lptr)) 
  341.         return 0;
  342.     free(*Lptr); 
  343.     *Lptr = FlexL0;
  344.     return 1;
  345. }
  346.  
  347.  
  348. /*  FlexList header functions  */
  349.  
  350. int FLsetMaxNodes(L, maxNodes)
  351. FlexL L;
  352. unsigned maxNodes;
  353. {
  354.     if (L)
  355.         if (maxNodes >= L->nodes)  {
  356.             L->maxNodes = maxNodes;
  357.             return 1;
  358.         }
  359.     return 0;
  360. }
  361.  
  362. int FLsetCompare(L, compare)
  363. FlexL L;
  364. int (*compare)(/* const void *D1, const void *D2 */);
  365. {
  366.     if (L)  {
  367.         L->compare = compare;
  368.         L->sorted = 0;
  369.         return 1;
  370.     }
  371.